컴퓨터 구조 기초
December 15, 2021
참고 링크 : ’👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖’
Microprocessor Cache
┌─────┐ address ┌─────── Cache ───────┐ ┌────────────┐ address ┌────────┐
| | ─────────────→ | | miss | | ─────────→ | |
| CPU | | - Cache Memory | ─────→ | Memory Bus | | Memory |
| | ←─── data ───→ | - Cache Controller | | | ←─ data ─→ | |
└─────┘ (cache hit) | | └────────────┘ └────────┘
↑ └─────────────────────┘ ↑
| ↑ |
| | update |
| | |
└───────────────────────────────┴─────────────────────────┘
data- 필요한 자료가 캐시에 있는 상황은 캐시 히트(hit), 없는 상황은 캐시 미스(miss) 라고 한다.
- 캐시 미스가 발생하면, CPU는 버스의 도움을 받아, 기억 장치에서 필요한 자료를 가져온다.
참고 자료
Virtual Memory(Memory Management)
┌─────┐ Virtual Address ┌─────┐ Physical Address ┌────────┐
| CPU | ────────────────→ | MMU | ─────────────────→ | Memory |
└─────┘ └─────┘ └────────┘- 가상 메모리는 ‘컴퓨터 저장 장치에 저장되어 있는 자료를 추상적으로 관리하는 기법’ 이다.
- 실제 기억 장치에서 유효한 주소는 물리 주소, 이를 단순화한 주소는 가상 주소라고 부른다.
- MMU(메모리 관리 장치) 는, 이러한 가상 주소를 다시 원래의 주소로 변환해주는 장치이다.
How to translate Virtual Adress to Physical Address!
┌─────────────┬────────┐
| Page Number | Offset | ← Virtual Address
└─────────────┴────────┘
| |
Translation |
↓ ↓
┌──────────────┬────────┐
| Frame Number | Offset | ← Physical Address
└──────────────┴────────┘- 기억 장치 공간을 일정한 크기로 나눠서 관리하는 가상 메모리 기법을, 페이징이라고 한다.
- 페이징 기법에서는, 기억 장치의 공간을 프레임 단위로 사용하고, 페이지 단위로 관리한다.
- 가상 주소와 물리 주소는 각각 페이지 번호와 오프셋, 프레임 번호와 오프셋으로 구성된다.
- 프레임 번호는 ‘자료가 기억 장치의 어느 프레임에 저장되어 있는지’ 를 나타내는 숫자이다.
- 오프셋은 ‘자료가 프레임의 어느 위치에 저장되어 있는지’ 를 더 자세히 나타내는 주소이다.
참고 자료
1. Basic Translation
Virtual Address => (Page Number + Offset)
┌───┬────────┐ (20bit) (12bit) -> 32bit(x86)
| i | Offset | ───────────────────────────────────────┐
└───┴────────┘ |
| |
| Page Table |
| ┌─────────────┬───────────────┐ |
| | Page Number | Frame Address | |
| |─────────────|───────────────| |
| ┌→ | ... | ... | ↓
| | |─────────────|───────────────| ┌───┬────────┐
└──┼→ | i | F | ────→ | F | Offset |
| |─────────────|───────────────| └───┴────────┘
└→ | ... | ... | Physical Address
└─────────────┴───────────────┘ (Frame Address + Offset)- 가상 주소를 물리 주소로 바꾸는 가장 기본적인 방법은, 페이지 테이블을 이용하는 것이다.
- 여기서, 페이지 테이블은 연속된 공간에 프레임 번호를 저장하는 배열 형태의 자료 구조다.
- 인덱스 번호는 배열의 인덱스와 마찬가지로 0번부터 시작하며, 페이지 번호로써 사용된다.
- 이러한 페이지 테이블의 각 공간에는, 프레임 번호에 대응되는 실제 물리 주소가 저장된다.
(이외에도, 선택 상태/변경 여부 플래그, 주소 공간, 프로세스 ID 등의 보조 정보도 포함된다.)
2. Two-level Paging
Main Memory
┌─────────────┬─────────────┬─────────────┐
| Frame | Frame | ... |
└─────────────┴─────────────┴─────────────┘
: :
┌──────────────────────┐
| Page Table |
└──────────────────────┘
└─────────────┘└───────┘
fetched overflow- 페이지 테이블의 크기가 프레임 크기보다 크면, 전체 엔트리에 직접적으로 접근할 수 없다.
- 이러한 문제는, ‘페이지 테이블을 다시 여러 페이지로 나누는 기법’ 을 통해 해결할 수 있다.
- 이러한 기법을 2단계(Two-level) 또는 다단계 페이징(Multi-level Paging) 이라고 부른다.
Virtual Address => (Page Number 1 + Page Number 2 + Offset)
┌───┬───┬────────┐ (10bit) (10bit) (12bit) -> 32bit(x86)
| i | j | Offset | ─────────────────────────────────────────────────────────────────┐
└───┴───┴────────┘ |
| | |
| └─────────────────────────┐ |
| | |
| Page Directory | pages of page table |
| ┌───────┬─────────────┐ | ┌─────────────────────────────┐ |
| | index | Page Number | | | ... | |
| |───────|─────────────| | ┌─────────────────────────────┐ | |
| | ... | ... | | | target page | | |
| |───────|─────────────| | ┌─────────────┬───────────────┐ | | |
└─→ | i | T | ─────→ | Page Number | Frame Address | | | |
|───────|─────────────| | |─────────────|───────────────| | | |
| ... | ... | | | ... | ... | | | ↓
└───────┴─────────────┘ | |─────────────|───────────────| |─┘ ┌───┬────────┐
↑ └──→ | j | F | ─────→ | F | Offset |
┌──────────────┐ |─────────────|───────────────|─┘ └───┴────────┘
| CR3 Register | | ... | ... | Physical Address
└──────────────┘ └─────────────┴───────────────┘ (Frame Address + Offset)- 다단계 페이징 기법에서, 여러 페이지로 나눠진 페이지 테이블은 주 기억 장치에 저장된다.
- 그리고, 그러한 페이지들이 저장된 프레임을, 새로운 페이지 테이블을 통해 관리하게 된다.
- 이러한 ‘페이지들이 저장된 프레임에 대한 외부 페이지 테이블’ 을 페이지 디렉터리라 한다.
Physical Address Space = 2^44 Byte
Virtual Address Space = 2^32 Byte
Page Entry Size = 4 Byte
Page Size = 4 KB
Number of Frame = (Physical Address Space) / (Page Size)
= 2^44 Byte / 2^12 Byte
= 2^32
Number of Pages of the Process = (Virtual Address Space) / (Page Size)
= 2^32 Byte / 2^12 Byte
= 2^20
Size of Page Table = (Number of Pages Of the Process) * (Page Entry Size)
= 2^20 * 4 Byte
= 2^22 Byte
= 4 MB- 페이지 테이블의 크기가 프레임 크기보다 크므로, 페이지 여러 개로 나눠서 관리해야 한다.
- 이러한 페이지 테이블에 대한 페이지는 다시 페이지 테이블(페이지 디렉터리) 로 관리된다.
- 외부에서 페이징을 보조하는 페이지 디렉터리를 외부 페이지 테이블이라고 부르기도 한다.
Number of Pages of Page Directory = (Size of Page Table) / (Page Size)
= 2^22 Byte / 2^12 Byte
= 2^22 * 2^-12
= 2^10
Size of Page Directory = (Number of Pages of Page Directory) * (Page Entry Size)
= 2^10 * 4 Byte
= 4 KB- 페이지 디렉터리의 크기가 프레임 한 칸에 들어갈 정도로 작아지면, 계층화를 멈추면 된다.
- 현재 예시의 경우, 다단계 페이징이 2단계에서 마무리되었기 때문에 2단계 페이징이 된다.
- 다단계 페이징은 이렇게, 계층화를 통해, 페이지 테이블의 크기를 줄이는 식으로 진행된다.
Virtual Address
┌─────────┬─────────┬─────────┬─────────┬────────┐
| Level 1 | Level 2 | ... | Level n | Offset |
└─────────┴─────────┴─────────┴─────────┴────────┘- 다단계 페이징 기법에서 가상 주소는, 각 단계의 주소 변환에 필요한 오프셋들로 구성된다.
- 이러한 오프셋은 이전 단계에서 얻은 기본 주소와 합쳐져서 다음 단계의 기본 주소가 된다.
Virtual Address
┌───────────────┬───────────────┬─────┬───────────────┬────────┐
| Level 1 | Level 2 | ... | Level n | Offset | ───────────────┐
└───────────────┴───────────────┴─────┴───────────────┴────────┘ |
| | | |
| ┌───────┐ | | Physical Address |
┌─→ + | ... | | | ┌──────────────┬────────┐ |
| | |───────| | | | Frame Number | Offset | ←┘
| └→ | entry | ─→ + ┌───────┐ | └──────────────┴────────┘
| |───────| | | ... | | ↑
| | ... | | |───────| | |
| └───────┘ └→ | entry | ─ ... ─→ + ┌───────┐ |
| |───────| | | ... | |
| | ... | | |───────| |
| └───────┘ └→ | entry | ─┘
| ┌──────────────────────────┐ |───────|
└── | Page Table Base Register | | ... |
└──────────────────────────┘ └───────┘- 각 페이지 테이블 엔트리에는, 주소 변환에 필요한 기본 주소(Base Address) 가 저장된다.
- 다단계 페이징이 n 단계 진행되었다고 하면 실제 프레임 주소는 n번째 테이블에 저장된다.
- 1단계 오프셋의 경우 페이지 테이블 기본 레지스터에 있는 페이지 테이블 주소와 합쳐진다.
(페이지 테이블 기본 레지스터는, 페이지 테이블의 시작 주소(Base) 를 저장하는 역할을 한다.) - n번째 주소 변환 결과인 실제 프레임의 주소와 기본 오프셋이 합쳐지면, 물리 주소가 된다.
참고 자료
3. TLB(Translation Look-Aside Buffer)
- 다단계 페이징 과정에서 생성되는 1 ~ n번 페이지 테이블은 모두 주 기억 장치에 저장된다.
- 즉, 특정 자료의 물리 주소를 얻기 위해서 주 기억 장치에 여러 번 접근해야 한다는 뜻이다.
- 다단계 페이징의 단계 수만큼 주소 변환 작업에 필요한 연산의 수도 증가하게 되는 것이다.
- 연산 횟수 증가는, 컴퓨터에서 실행되는 프로그램에 대한, 전체적인 성능 저하로 이어진다.
- 이러한 문제에 대한 해결책으로 등장한 것이, 초고속 기억 장치인 변환 색인 버퍼(TLB) 다.
- 변환 색인 버퍼는 내용 주소화 기억 장치(Content-addressable memory) 로써 구현된다.
Fully Associative
┌─────┬─────┬───────┬──────┬──────┐
| VPN | FPN | valid | prot | ASID |
└─────┴─────┴───────┴──────┴──────┘
VPN = virtual page number
FPN = physical frame number
valid = valid bit
prot = protection bit
ASID = address space identifier- 정리용 자료
Now the question is where to place the page table, such that overall access time (or reference time) will be less.
The problem initially was to fast access the main memory content based on address generated by CPU (i.e logical/virtual address).
Initially, some people thought of using registers to store page table, as they are high-speed memory so access time will be less.
The idea used here is, place the page table entries in registers, for each request generated from CPU (virtual address), it will be matched to the appropriate page number of the page table, which will now tell where in the main memory that corresponding page resides.
Everything seems right here, but the problem is register size is small (in practical, it can accommodate maximum of 0.5k to 1k page table entries) and process size may be big hence the required page table will also be big (lets say this page table contains 1M entries), so registers may not hold all the PTE’s of Page table.
So this is not a practical approach.
Is TLB software or hardware?
-> The TLB is a hardware cache which is usually implemented as a content addressable memory (CAM), also called a fully associative cache.
내용 주소화 기억장치(Content-addressable memory)
매우 빠른 속도를 요하는 탐색 애플리케이션에서 사용되는 특수한 메모리
연관 메모리(associative memory), 연관기억장치라고도 함
A fully associative cache contains a single set with B ways, where B is the number of blocks.
A memory address can map to a block in any of these ways.
A fully associative cache is another name for a B-way set associative cache with one set.
Fully Associative Cache
쉽게 설명하면 비어있는 캐시메모리가 있으면 그냥 마음대로 주소를 저장하는 방식
즉 저장시 크게 알고리즘 비용이 없어 간단한데, 찾을 때 문제
모든 블럭을 순회해 데이터가 있는지 검사
이를 위해 CAM(content Addressable memory)라는 특수한 형태의 메모리 구조를 사용하는데, 가격이 비쌈Flow
┌─────┐ ┌─────────────────────────────────┐ hit ┌───────┐ miss ┌────────┐
| CPU | ──→ | TLB lookup with virtual address | ────→ | Cache | ─────→ | Memory |
└─────┘ └─────────────────────────────────┘ └───────┘ └────────┘
↑ | ↑ | |
| | miss | | |
| ↓ | | |
| ┌───────────────────────────────────┐ | | hit |
| | translate address with page table | ───────┘ | |
| └───────────────────────────────────┘ | |
| | |
| ┌──────────────────────────────┐ ↓ |
└────────────── | find data and send it to CPU | ←──────────────────────┘
└──────────────────────────────┘Cached MMU Memory Overview
Memory access sequence in the ARM architecture
┌──────────┐ ┌─────────────┐ ┌────────┐
| Access | Access bits, domain ┌─────┐ | Translation | | |
| control | ←──────────────────── | | ←────────→ | table walk | ←────────→ | |
| hardware | | | | hardware | | |
└──────────┘ | TLB | └─────────────┘ | |
| | | | |
| ┌────────────→ | | ───────────┬────────────────────────→ | |
| Abort | └─────┘ | Physical address | Main |
| | | | (PA) | memory |
| | | C, B bits | | |
↓ | ↓ | | |
┌─────┐ | ┌──────────────┐ | ┌────────────┐ | |
| | | | Cache | └───→ | Cache | | |
| ARM | ──────────┴─────────→ | and | | line fetch | ←───→ | |
| | Virtual address | write buffer | ←────────→ | hardware | | |
└─────┘ (VA) └──────────────┘ └────────────┘ └────────┘┌─────┐
| CPU | ←─────────────────────────────────────────────┬────────────────┐
└─────┘ | |
| | ┌────────┐ ┌─────────┐
| ┌───────┐ miss | Main | miss | Storage |
| ┌──────────────────→ | Cache | ─────→ | Memory | ─────→ | (Disk) |
| Virtual address | Physical Address └───────┘ └────────┘ └─────────┘
| | (hit) ↑
| | | Physical Address
↓ | |
┌─────┐ Virtual address ┌─────┐ ┌────────────┐
| MMU | ────────────────→ | TLB | ────────────→ | Page Table |
└─────┘ (hit) └─────┘ (miss) └────────────┘
# Computer Science